/*
 * @lc app=leetcode.cn id=413 lang=cpp
 *
 * [413] 等差数列划分
 */

// @lc code=start
class Solution
{
public:
  int numberOfArithmeticSlices(vector<int>& nums)
  {
    int n = nums.size();
    if (n < 3)
      return 0;
    vector<pair<int, int>> dp(n);
    int ans = 0;
    dp[1]   = make_pair(nums[1] - nums[0], 0);
    for (int i = 2; i < n; ++i) {
      int cur_cnt = 0;
      int d = nums[i] - nums[i - 1];
      // 子数组长度为3
      if (d == nums[i - 1] - nums[i - 2])
        ++cur_cnt;
      // 子数组长度 > 3
      if (dp[i - 1].first == d)
        cur_cnt += dp[i - 1].second;
      ans += cur_cnt;
      dp[i].first = d;
      dp[i].second = cur_cnt;
    }
    return ans;
  }
};
// @lc code=end
